﻿using System;
using System.Collections.Generic;

namespace KDTree
{
	class Block
	{
		public int Id;
		public int x, y, w, h;
		public int GetRight()
		{
			return x + w;
		}
		public int GetTop()
		{
			return y + h;
		}
		public void SetX(int x1)
		{
			var r = x + w;
			x = x1;
			w = r - x1;
		}
		public void SetY(int y1)
		{
			var t = y + h;
			y = y1;
			h = t - y1;
		}
		public void SetRight(int r)
		{
			w = r - x;
		}
		public void SetTop(int t)
		{
			h = t - y;
		}
		public override string ToString()
		{
			return string.Format("[Block]{0},{1},{2},{3},{4}", Id, x, y, w, h);
		}

	}

	class TreeNode
	{
		public TreeNode lb, lt, rb, rt;
		private List<Block> children;
		private Block boundBox;
		private static int minSize;
		private static int maxDepth;
		private TreeNode parent;
		private int depth = 0;
		private Block GetBoundBox()
		{
			var bc = new Block();
			var c = children[0];
			bc.x = c.x;
			bc.y = c.y;
			bc.w = c.w;
			bc.h = c.h;

			foreach (var b in children)
			{
				if (b.x < bc.x)
				{
					bc.SetX(b.x);
				}
				if (b.y < bc.y)
				{
					bc.SetY(b.y);
				}
				if (b.GetRight() > bc.GetRight())
				{
					bc.SetRight(b.GetRight());
				}
				if (b.GetTop() > bc.GetTop())
				{
					bc.SetTop(b.GetTop());
				}
			}

			return bc;
		}

		private static bool CheckBlockOverlap(Block container, Block b)
		{
			return !((container.x + container.w) < b.x
			         ||container.x > (b.x+b.w)
			         || (container.y+container.h) < b.y
			         || container.y > (b.y+b.h));
		}

		private void SelectNodes(List<Block> blocks)
		{
			this.children = new List<Block>();
			foreach (var b in blocks)
			{
				var ret = CheckBlockOverlap(this.boundBox, b);
				if (ret)
				{
					this.children.Add(b);
				}
			}
		}


		private void CutIntoFourNode()
		{
			if (this.children.Count <= 1)
			{
				return;
			}
			if (this.boundBox.w <= TreeNode.minSize || this.boundBox.h <= TreeNode.minSize)
			{
				return;
			}
			if (this.depth >= TreeNode.maxDepth)
			{
				return;
			}
				
			lb = new TreeNode();
			lb.parent = this;
			lb.depth = this.depth+1;
			lb.boundBox = new Block()
			{
				x = this.boundBox.x,
				y = this.boundBox.y,
				w = (this.boundBox.w+1)/2,
				h = (this.boundBox.h+1)/2,
			};
			lb.SelectNodes(this.children);

			lt = new TreeNode();
			lt.parent = this;
			lt.depth = this.depth+1;
			lt.boundBox = new Block()
			{
				x = this.boundBox.x,
				y = this.boundBox.y+this.boundBox.h/2,
				w = (this.boundBox.w+1)/2,
				h = (this.boundBox.h+1)/2,
			};
			lt.SelectNodes(this.children);


			rb = new TreeNode();
			rb.parent = this;
			rb.depth = this.depth+1;
			rb.boundBox = new Block()
			{
				x = this.boundBox.x + this.boundBox.w / 2,
				y = this.boundBox.y,
				w = (this.boundBox.w + 1) / 2,
				h = (this.boundBox.h + 1) / 2,
			};
			rb.SelectNodes(this.children);

			rt = new TreeNode();
			rt.parent = this;
			rt.depth = this.depth+1;
			rt.boundBox = new Block()
			{
				x = this.boundBox.x + this.boundBox.w / 2,
				y = this.boundBox.y + this.boundBox.h / 2,
				w = (this.boundBox.w + 1) / 2,
				h = (this.boundBox.h + 1) / 2,
			};
			rt.SelectNodes(this.children);

			lb.CutIntoFourNode();
			lt.CutIntoFourNode();
			rb.CutIntoFourNode();
			rt.CutIntoFourNode();
		}


		public static TreeNode BuildTree( List<Block> blocks, int ms, int md)
		{
			var root = new TreeNode();
			root.children = blocks;
			TreeNode.minSize = ms;
			TreeNode.maxDepth = md;
			root.boundBox = root.GetBoundBox();
			root.CutIntoFourNode();

			return root;
		}

		public static void PrintTree(TreeNode root)
		{
			Queue<TreeNode> nodes = new Queue<TreeNode>();
			nodes.Enqueue(root);

			while (nodes.Count > 0)
			{
				var n = nodes.Dequeue();
				Console.WriteLine(string.Format("Tree:{0},{1},{2},{3},{4},{5}", n.depth, n.children.Count, n.boundBox.x, n.boundBox.y, n.boundBox.w, n.boundBox.h));
				var ch = "Child:";
				foreach(var c in n.children)
				{
					ch += c.Id + ",";
				}
				Console.WriteLine(ch);

				if (n.lb != null)
				{
					nodes.Enqueue(n.lb);
				}

				if (n.lt != null)
				{
					nodes.Enqueue(n.lt);
				}

				if (n.rb != null)
				{
					nodes.Enqueue(n.rb);
				}

				if (n.rt != null)
				{
					nodes.Enqueue(n.rt);
				}
			}
		}


		public List<Block> CollisionBlock(Block a)
		{
			if (children.Count == 0)
			{
				return new List<Block>();
			}
			if (!CheckBlockOverlap(boundBox, a))
			{
				return new List<Block>();
			}
			if (lb == null && lt == null && rb == null && rt == null)
			{
				var ret1 = new List<Block>();

				foreach (var b in children)
				{
					if (CheckBlockOverlap(b, a))
					{
						ret1.Add(b);
					}
				}
				return ret1;
			}

			List<Block> ret = new List<Block>();
			if (lb != null)
			{
				ret.AddRange(lb.CollisionBlock(a));
			}
			if (lt != null)
			{
				ret.AddRange(lt.CollisionBlock(a));
			}

			if (rb != null)
			{
				ret.AddRange(rb.CollisionBlock(a));
			}


			if (rt != null)
			{
				ret.AddRange(rt.CollisionBlock(a));
			}

			return ret;
		}
	}


	class MainClass
	{
		public static void Main(string[] args)
		{
			//minZone
			//zone 至少1个node
			var blockList = new List<Block>()
			{
				new Block(){x=-46390, y=-53190, w=18100, h=18100, Id=1},
				new Block(){x=-28260, y=-53190, w=18100, h=18100, Id=2},
				new Block(){x=-10140, y=-35060, w=18100, h=18100, Id=3},
			};
			//37435, 44235,
			var root = TreeNode.BuildTree( blockList, 19000, 10);
			TreeNode.PrintTree(root);

			var block = new Block()
			{
				x= -30000,
				y = -50000,
				w = 10000,
				h = 10000,
			};
			var ret = root.CollisionBlock(block);
			foreach (var b in ret)
			{
				Console.WriteLine(b.ToString());
			}
		}
	}
}
